package 面试经典150题.数组;

/**
 * @author tmh
 * @date 2024/7/1 20:11
 * @description
 */
public class T238除自身以外数组的乘积 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        productExceptSelf(nums);
    }

    //以前在做这个题的时候，老是搞不清楚边界的处理，看到别的题解说：先求下三角或者再求上三角之类的。
// 今天正好借着【每日一题】系列，终于给搞懂了，不用管上三角或者下三角。见下图就知道了：
//
//原数组：       [1       2       3       4]
//左部分的乘积：   1       1      1*2    1*2*3
//右部分的乘积： 2*3*4    3*4      4      1
//结果：        1*2*3*4  1*3*4   1*2*4  1*2*3*1
/*    public static int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        if (len == 0){
            return new int[0];
        }
        int[] ans = new int[len];
        ans[0] = 1;
        int tmp = 1;
        for (int i = 1; i < len; i++) {
            //左面部分的乘积分别是上和下相乘(第一排和第二排的前一个数子)
            ans[i] = ans[i - 1] * nums[i - 1];
        }
        for (int i = len - 2; i >= 0; i--) {
            //右部分的乘积也是上下相乘(第一排和第三排的前一个数子)
            tmp *= nums[i + 1];
            ans[i] *= tmp;
        }
        return ans;
    }*/
    public static int[] productExceptSelf(int[] nums) {
        if (nums.length == 0) {
            return new int[0];
        }
        //定义一个新的数组ans[],定义一个tmp=1
        int len = nums.length;
        int[] ans = new int[len];
        //ans先保存的是左面部分的乘积
        ans[0] = 1;
        //temp一开始表示的是最后一个数的右部分的乘积
        int temp = 1;
        for (int i = 1; i < len; i++) {
            //计算其他数字左部分的乘积
            ans[i] = ans[i - 1] * nums[i - 1];
        }
        //计算其他数字右部分的乘积，并更新ans里面最后的结果
        for (int i = len - 2; i >= 0; i--) {
            //计算右面部分的乘积，然后重新赋值给temp
            temp = temp * nums[i + 1];
            //更新ans==》左面部分的乘积*右面部分的乘积
            ans[i] = temp * ans[i];
        }
        return ans;
    }

}
